/*
 * @lc app=leetcode.cn id=45 lang=javascript
 *
 * [45] 跳跃游戏 II
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
// var jump = function(nums) {
//   if(nums.length <= 1) return 0;
//   let pre = 0; let next = pre; let count = 0;
//   while(next < nums.length - 1){
//     if(pre + nums[next] >= nums.length - 1) return ++count;

//     let max = pre + nums[pre];
//     for (let i = pre + 1; i <= pre + nums[pre]; i++) {
//       if(i + nums[i] > max){
//         max = i + nums[i];
//         next = i;
//       }
//     }
//     console.log(next)
//     pre = next;
//     count++;
//   }
//   return count;
// };

/**
 * 复习 2021-08-04
 */
var jump = function (nums) {
  if (nums.length < 2) return 0;
  let ret = 0; // 跳跃次数
  for (let i = 0; i < nums.length;) {
    let tail = i + nums[i];  // 当前位置可跳跃的最远位置
    if (tail >= nums.length - 1) return ++ret; // 如果可跳跃的最远位置大于最后位置，返回跳跃次数

    // 假设从i位置跳跃到j位置，可保证从j再往后跳跃，得到的距离最大
    // 也就是寻找从 i 跳到 j，再从j 跳跃一次可得到最远距离的 j 位置。
    let max = 0;
    for (let j = i + 1; j <= tail; j++) {
      if (j + nums[j] > max) {
        max = j + nums[j];
        i = j;
      };
    }
    ret++;
  }
  return ret;
}
// @lc code=end

